package 剑指专题.其他;


/*
 * Author：江松
 * Date：2023/4/3 20:12
 *
 整数1-n中1的个数:
 1,暴力枚举O(n*log10 n)
 2,数学:
 3，分类讨论：51321——以百位为例,cur为当前位(n/base%10),a=(n/base/10),b=(n%base)
 要计算cur这位为1时的数的个数，只是这位数，不考虑其他位，因此不重复，进行分类讨论。
 也就是一个排列组合问题，a部分*b部分
 cur=0，说明只能向前借位，res=a*base
 cur=1,不用借位的+借位的，res=(b+1)+(a*base)
 cur>1，本位自己就能使得b取值0-99(也就是base),res=(a+1)*base
 */

public class Main6 {
    public int NumberOf1Between1AndN_Solution(int n) {
        int a,b,base=1,cur;
        int res=0;
        while(base<=n){
            a=n/base/10;
            b=n%base;
            cur=n/base%10;
            if(cur==0){
                res+=a*base;
            }else if(cur==1){
                res+=a*base+b+1;
            }else{
                res+=(a+1)*base;
            }
            base*=10;
        }
        return res;
    }
}
